package q873_lenLongestFibSubseq;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    需要同时结合hash表和dp的方式来解决该问题
    dp[i][j] 表示以 最后两个值是 arr[i], arr[j] 的最长严格递增斐波那契子序列
    首先从暴力方法考虑 只需要循环三次
    ——————————————————————————————————
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < i && arr[i] + arr[k] <= arr[j]; ++k) {
                if (arr[k] + arr[i] == arr[j]) dp[i][j] = Math.max(3, Math.max(dp[k][i] + 1, dp[i][j]));
            }
            ans = Math.max(ans, dp[i][j]);
        }
    }
    ——————————————————————————————————

    也能够解决问题 但是时间复杂度过高 因此需要考虑hash表优化
    使用一个hash表存储所有数组中元素及对应的位置 由于斐波那契数列是需要 arr[k] + arr[j] = arr[i] 题目中已经给出了严格递增的数组
    我们假设是k < j < i 那么同样有arr[k] = arr[i] - arr[j] 所以查找第三个数字时 只需要使用map的containsKey即可
    不需要多一重循环  同时需要考虑的是 斐波那契数列至少需要三个数 而数组初始化时都是0 所以当找到一个满足map.containsKey(arr[i] - arr[j])
    此时要考虑dp[j][i] = Math.max(3, dp[map.get(arr[i] - arr[j])][j] + 1); 也就是至少能够构成一个3个数字的斐波那契数列
    */
    public int lenLongestFibSubseq(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) map.put(arr[i], i);
        int ans = 0;
        int[][] dp = new int[arr.length][arr.length];
        for (int i = 2; i < arr.length; ++i) {
            // 由于 arr[k] + arr[j] = arr[i] arr[k] < arr[j] 所以可以用2 * arr[j] > arr[i]来优化循环
            for (int j = i - 1; j >= 0 && (2 * arr[j] > arr[i]); --j) {
                if (map.containsKey(arr[i] - arr[j])) {
                    dp[j][i] = Math.max(3, dp[map.get(arr[i] - arr[j])][j] + 1);
                }

                ans = Math.max(ans, dp[j][i]);
            }
        }

        return ans;
    }
}
